package com.example.myletcodelearing.one

import java.util.*

/**
 * @author tgw
 * @date 2022/11/7
 * @describe https://leetcode-cn.com/problems/perfect-squares/   *搜索：完全平方数

 *
 * 广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。
 *
 * 算法流程如下：
将数字 N 转换为多树，按树的层次遍历即可（分解出 N 可能的组合），每一层的节点 = 用上一层的节点 - 完全平方数

1.新建一个 queue，用来存储访问的每个节点
2.用 HashSet 过滤掉计算过的组合，避免重复计算
3.循环判断队列是否为空，如果队列为空即循环终止
4.获取每层的长度，遍历每一层，计算出下一层的组合，添加到 queue
5.重复执行 3、4
6.遍历结束时，层数即是能组成完全平方数的最少个数
 */
fun main(args: Array<String>) {

    //几个数的平方和 值相加等于目标值 如 3=1²+1²+1²，4=2²
    var land = Solution8Bfs.Solution()

   var num = land.numSquares(30) //等于3
//   var num = land.numSquares(3) //等于1 因为只要一个2²就行，所以数量是1
    print("完全平方数：$num")
}
private class Solution8Bfs {

    class Solution {
        fun numSquares(n: Int): Int {
            val square = arrayListOf<Int>()
            val sqrt = Math.sqrt(n.toDouble()).toInt()
            for (i in 1..sqrt) {
                square.add(i * i)
            }

            var step = 0
            val result = hashSetOf<Int>()
            val queue = LinkedList<Int>()
            queue.offer(n)
            while (!queue.isEmpty()) {
                step += 1
                val count = queue.size
                for (i in 0 until count) {
                    val target = queue.poll();
                    loop@ for (item in square) {
                        //when 函数用法
                        when {
                            target == item -> {
                                return step
                            }
                            item > target -> {
                                break@loop;
                            }
                            else -> {
                                val sub = target - item
                                if (result.add(sub))
                                    queue.offer(sub)

                            }
                        }

                    }
                }
            }
            return step
        }
    }

}